/**
 * @author zjkermit
 * @email zjkermit@gmail.com
 * @date Mar 12, 2014
 */
package zhoujian.oj.leetcode;

import java.util.ArrayList;

import org.junit.Test;

/**
 * @version 1.0
 * @description Given a matrix of m x n elements (m rows, n columns), return all
 *              elements of the matrix in spiral order.
 * 
 *              For example, Given the following matrix:
 *              [ 
 *              	[ 1, 2, 3 ], 
 *              	[ 4, 5, 6 ], 
 *              	[ 7, 8, 9 ] 
 *              ] 
 *              
 *              You should return [1, 2, 3, 6, 9, 8, 7, 4, 5].
 */
public class SpiralMatrix {

	// my solution
	boolean[][] marked;
	int m;
	int n;
	int direct;
	
	public ArrayList<Integer> spiralOrder(int[][] matrix) {
		ArrayList<Integer> res = new ArrayList<Integer>();
		this.m = matrix.length;
		if (m == 0)
			return res;
		this.n = matrix[0].length;
		if (n == 0)
			return res;
		marked = new boolean[m][n];
		int i = 0;
		int j = 0;
		res.add(matrix[i][j]);
		marked[i][j] = true;
		direct = 1;
		while (true) {
			switch (direct) {
				// '1' means to right
				case 1 : {
					if (check(i, j + 1)) {
						marked[i][++j] = true;
						res.add(matrix[i][j]);
					} else 
						direct = 2;
				} break;
				// '2' means to bottom
				case 2 : {
					if (check(i + 1, j)) {
						marked[++i][j] = true;
						res.add(matrix[i][j]);
					} else 
						direct = 3;
				} break;
				// '3' means to left
				case 3 : {
					if (check(i - 1, j)) {
						marked[--i][j] = true;
						res.add(matrix[i][j]);
					} else 
						direct = 4;
				} break;
				// '4' means to top
				case 4 : {
					if (check(i, j - 1)) {
						marked[i][--j] = true;
						res.add(matrix[i][j]);
					} else 
						direct = 1;
				} 
				default : {
					if (!check(i, j + 1) && !check(i + 1, j) && !check(i - 1, j) && !check(i, j - 1))
						return res;
				}
			}
		}
    }
	
	private boolean check(int i, int j) {
		if (i < 0 || i > m -1 || j < 0 || j > n - 1)
			return false;
		else 
			return !marked[i][j];
	}
	
	// solution 2
	public ArrayList<Integer> solution2(int[][] matrix) {  
        ArrayList<Integer> res = new ArrayList<Integer>();  
        int m = matrix.length;  
        if (m == 0)  
            return res;  
        int n = matrix[0].length;  
        if (n == 0)  
            return res;  
        int min = m < n ? m : n;  
        int layer = min / 2;  
        for (int i = 0; i < layer; i++) {  
            for (int j = i; j < n - 1 - i; j++)  
                res.add(matrix[i][j]);  
            for (int j = i; j < m - 1 - i; j++)  
                res.add(matrix[j][n - 1 - i]);  
            for (int j = n - 1 - i; j > i; j--)  
                res.add(matrix[m - 1 - i][j]);  
            for (int j = m - 1 - i; j > i; j--)  
                res.add(matrix[j][i]);  
        }  
        if (min % 2 == 1) {  
            if (m > n)  
                for (int i = layer; i <= m - 1 - layer; i++)  
                    res.add(matrix[i][n / 2]);  
            else  
                for (int i = layer; i <= n - 1 - layer; i++)  
                    res.add(matrix[m / 2][i]);  
        }  
        return res;  
    }  
	
	// solution 3, similar to my solution
	public ArrayList<Integer> solution3(int[][] matrix) {  
        ArrayList<Integer> res = new ArrayList<Integer>();  
        if (matrix.length == 0)  
            return res;  
        int beginX = 0, endX = matrix[0].length - 1;  
        int beginY = 0, endY = matrix.length - 1;  
        while (true) {  
            // From left to right  
            for (int i = beginX; i <= endX; ++i)  
                res.add(matrix[beginY][i]);  
            if (++beginY > endY)  
                break;  
            // From top down  
            for (int i = beginY; i <= endY; ++i)  
                res.add(matrix[i][endX]);  
            if (beginX > --endX)  
                break;  
            // From right to left  
            for (int i = endX; i >= beginX; --i)  
                res.add(matrix[endY][i]);  
            if (beginY > --endY)  
                break;  
            // From bottom up  
            for (int i = endY; i >= beginY; --i)  
                res.add(matrix[i][beginX]);  
            if (++beginX > endX)  
                break;  
        }  
        return res;  
    }  
	
	@Test
	public void test() {
		int[][] matrix = new int[][] { 
				{1, 2, 3, 4}, 
				{12, 13, 14, 5}, 
				{11, 16, 15, 6},
				{10, 9, 8, 7} };
		System.out.println("my solution");
		for (int i : spiralOrder(matrix)) {
			System.out.print(i + " ");
		}
		System.out.println("\nsolution2");
		for (int i : solution2(matrix)) {
			System.out.print(i + " ");
		}
		System.out.println("\nsolution3");
		for (int i : solution3(matrix)) {
			System.out.print(i + " ");
		}

	}
	
}
